#include "StdAfx.h"
#include "binTreeNode.h"


binTreeNode::binTreeNode(int val):
  _pleft(0), _pright(0), _val(val)
{
}


binTreeNode::~binTreeNode(void)
{
}

binTreeNode* binTreeNode::left()
{
	return _pleft;
}
binTreeNode* binTreeNode::right()
{
	return _pright;
}
void binTreeNode::setLeft(binTreeNode* left)
{
	_pleft = left;
}
void binTreeNode::setRight(binTreeNode* right)
{
	_pright = right;
}

void prePrint( binTreeNode* node )
{
	if( node == 0 )
		return;
	cout << node->val() << endl;

	prePrint( node->left() );
	prePrint( node->right() );
	
}

void prePrint_iter( binTreeNode* node )
{
	stack<binTreeNode*> s;
	binTreeNode* current = node;
	//bool isDone = false;
	while( !s.empty() || current !=0 )
	{
		if(current)
		{
			cout << current->val() << ",";
			if( current->right() )
				s.push(current->right());
			current = current->left();
			
		}
		else
		{
			current = s.top();
			//cout << current->val() << ",";
			s.pop();
		}

	}
	cout << endl;
}

void postPrint( binTreeNode* node )
{
	if( node == 0 )
		return;
	postPrint( node->left() );
	postPrint( node->right() );
	cout << node->val() << endl;
}
void inPrint( binTreeNode* node )
{
	if( node == 0 )
		return;
	inPrint( node->left() );
	cout << node->val() << endl;
	inPrint( node->right() );
}

void inPrint_iter( binTreeNode* node )
{
	stack<binTreeNode*> s;
	binTreeNode* current = node;
	while( !s.empty() || current != 0)
	{
		if( current != 0 )
		{
			s.push(current);
			current = current->left();
		}
		else
		{
			current = s.top();
			cout << current->val() << ",";
			s.pop();
			current = current->right();
		}
	}
	cout << endl;
}
int printAtLevel( binTreeNode* node, int level)
{
	if( node == 0 || level < 0 )
		return 0 ;
	if( level == 0 )
	{
		cout << node->val() << endl;
		return 1;
	};

	return printAtLevel( node->left(), level-1) + printAtLevel( node->right(), level -1 );
}

void rebuild( int* preArr, int* inArr, int len, binTreeNode* root)
{
	if (preArr == 0 || inArr == 0 )
		return;

	if( root == 0 )
	{	
		cout << "Need node" << endl;
		return;
	}
	
	root->setVal(*preArr);

	if( len <= 1 )
		return;
	
	//go through inArr to find the root element, left to it the left tree
	int leftChildLen = 0, rightChildLen = 0;
	for( int* d = inArr; *d != *preArr && leftChildLen < len; ++d)
	{
		leftChildLen++;
	}

	rightChildLen = len - leftChildLen -1;

	if( leftChildLen > 0 )
	{
		binTreeNode* node = new binTreeNode();
		rebuild( preArr+1, inArr, leftChildLen, node);
		root->setLeft(node);
	}
	if( rightChildLen > 0 )
	{
		binTreeNode* node = new binTreeNode();
		rebuild( preArr+ leftChildLen+ 1, inArr+ leftChildLen+ 1, rightChildLen, node);
		root->setRight(node);
	}

}
//Return the number of node and the number of leave in one function
void num_node_leave( binTreeNode* root, int& num_node, int& num_leaf)
{
	if( root == 0 )
	{
		return;
	}

	if( root->is_leaf() )
		num_leaf++;
	num_node++;

	num_node_leave( root->left(), num_node, num_leaf);
	num_node_leave( root->right(), num_node, num_leaf);
}

//determine whether a binary tree is BST
//call with isBst(node, numberic_limits<int>.min, numberic_limits<int>.max);
bool isBst(binTreeNode* node, int min, int max)
{
	if( node == 0 ) return true;
	bool leftresult =  true, rightresult = true;
	if( min <= node->val() || max >= node->val() )
		return false;

	//if(node->left()) //no need to determin null at all
	//{
		leftresult = isBst( node->left(), min, node->val()); 
	//}

	//if(node->left())
	//{
		rightresult = isBst( node->left(), node->val(), max); 
	//}

	return leftresult && rightresult;
}